package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * https://leetcode.com/problems/task-scheduler/
 * <p>
 * 错误写法
 * step = 1
 * A 4
 * B 3
 * C 2
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC621 implements Greedy {
    public int leastInterval(char[] tasks, int n) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int c : tasks) {
            counts.compute(c, (key, oldValue) -> oldValue == null ? 1 : oldValue + 1);
        }
        List<Integer> cnts = counts.values().stream()
                .sorted(Comparator.reverseOrder()).collect(Collectors.toList());
        //至此, cnts里面是倒叙的任务个数 如: 3,3
        System.out.println(cnts);

        int totalTime = 0;
        int remainEmptys = 0;
        int lastNewSeg = cnts.get(0);//-1base
        for (Integer cnt : cnts) {
            int canTake = Math.min(Math.min(cnt, lastNewSeg), remainEmptys);
            remainEmptys = remainEmptys - canTake;
            cnt = cnt - canTake;
            if (cnt == 1) {
                totalTime++;
            } else if (cnt > 1) {
                remainEmptys += (cnt - 1) * n;
                lastNewSeg = cnt - 1;
                totalTime += remainEmptys + cnt;
            }
        }
        return totalTime;
    }

    public static void main(String[] args) {
//        System.out.println(new LC621().leastInterval(new char[]{'A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E'}, 4));//10
//        System.out.println(new LC621().leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B'}, 2));//8
//        System.out.println(new LC621().leastInterval(new char[]{'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'}, 2));//16
        System.out.println(new LC621().leastInterval(new char[]{
                'A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'E'}, 2));//16
        //FIXME 至此, 代码确实已经是按照我的思路来的了,
        // ABC ABC ABC DE_D 3 3 3 2 1
        // 但是 这个致命的testcase, 说明我这波贪心根本没贪对, 思路就是错误的!!


        //FIXME 这种贪法不对, 想到了另一种, 这样安排
        // ABCDE ABCD ABC
        // 如何证明贪心思路是正确的呢??
        // 两种方案一个区别, 比如我有很多A, 上面思路是两个任务A之间尽量近 下面思路是两个A之间尽量远??

        // FIXME 啊哈, 又一种思路, 尽量让idle的地方最少

    }
    /*
    //key是空位长度1-n, value是个数; 1: 3, 2: 2 -> 3个长度1的空位, 2个长度2的空位.
        TreeMap<Integer, Integer> emptys = new TreeMap<>();
        while (emptys.lastEntry() != null && cnt > 0) {
            if (emptys.lastEntry().getValue() > cnt) {//足够
                emptys.lastEntry().setValue(emptys.lastEntry().getValue() - cnt);
                cnt = 0;//break;
            } else {
                cnt = cnt - emptys.lastEntry().getValue();
                emptys.pollLastEntry();
            }
        }
        if (cnt > 0) {
            emptys.put(n - 1, cnt - 1);
        }
    * */
}
